\relax 
\emailauthor{correa@lia.ufc.br}{Ricardo C. Corr\^{e}a}
\emailauthor{ddelledo@ungs.edu.ar}{Diego Delle Donne}
\emailauthor{ikoch@ungs.edu.ar}{Ivo Koch}
\emailauthor{jmarenco@ungs.edu.ar}{Javier Marenco\corref {cor1}}
\citation{Bomze99themaximum}
\citation{Segundo.Losada.Jimenez.11,Tomita.Kameda.07}
\citation{Atamturk200040}
\citation{ManninoSassano96}
\citation{LovaszPlummer86}
\citation{ManninoSassano96}
\citation{Rossi.Smriglio.01}
\citation{Pardalos}
\select@language{english}
\@writefile{toc}{\select@language{english}}
\@writefile{lof}{\select@language{english}}
\@writefile{lot}{\select@language{english}}
\Newlabel{ufcdc}{a}
\Newlabel{sarmiento}{b}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
\citation{LovaszPlummer86}
\citation{Rossi.Smriglio.01}
\citation{XavierCampelo11}
\citation{XavierCampelo11}
\@writefile{toc}{\contentsline {section}{\numberline {2}The maximum stable set polytope}{2}}
\newlabel{eq:ineq}{{1}{2}}
\newlabel{lem:upalphac}{{1}{2}}
\citation{LovaszPlummer86}
\citation{Pardalos,Rossi.Smriglio.01}
\citation{Rossi.Smriglio.01}
\citation{ManninoSassano96}
\citation{XavierCampelo11}
\@writefile{toc}{\contentsline {section}{\numberline {3}Clique projection}{3}}
\newlabel{lem:edgeG1}{{2}{3}}
\newlabel{lem:alphaproj}{{3}{3}}
\newlabel{coro:alphaproj}{{1}{3}}
\citation{XavierCampelo11}
\newlabel{fig:decrease}{{1(a)}{4}}
\newlabel{sub@fig:decrease}{{(a)}{4}}
\newlabel{fig:equal}{{1(b)}{4}}
\newlabel{sub@fig:equal}{{(b)}{4}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Examples of the two cases of Lemma~\ref  {lem:alphaproj} with $W = \{ f, g, h \}$. In~\ref  {sub@fig:notrank}, $\alpha (G) = \alpha (H[V \setminus (N_W \cup W)]) + 1$, whereas $\alpha (G) = \alpha (H[V \setminus (N_W \cup W)])$ in~\ref  {sub@fig:rank}, where $H = G \mid W$.}}{4}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {{$\alpha (G) = 3$} and {$\alpha (H[V \setminus (N_W \cup W)]) = 2$}, where $H = G \mid W$.}}}{4}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {{$\alpha (G) = \alpha (H[V \setminus (N_W \cup W)]) = 3$}, where $H = G \mid W$.}}}{4}}
\newlabel{fig:alphaproj}{{1}{4}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Clique-Lifting}{4}}
\newlabel{sec:clique-lift}{{4}{4}}
\newlabel{eq:validineq}{{2}{4}}
\newlabel{eq:lifted}{{3}{4}}
\newlabel{eq:lambda}{{4}{4}}
\newlabel{lem:lifting}{{4}{4}}
\citation{XavierCampelo11}
\newlabel{newfig:decrease}{{2(a)}{5}}
\newlabel{sub@newfig:decrease}{{(a)}{5}}
\newlabel{newfig:equal}{{2(b)}{5}}
\newlabel{sub@newfig:equal}{{(b)}{5}}
\newlabel{newfig:decrease}{{2(c)}{5}}
\newlabel{sub@newfig:decrease}{{(c)}{5}}
\newlabel{newfig:equal}{{2(d)}{5}}
\newlabel{sub@newfig:equal}{{(d)}{5}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Examples of the two cases of Lemma~\ref  {lem:alphaproj} with $W = \{ f, g, h \}$. In~\ref  {sub@fig:notrank}, $\alpha (G) = \alpha (H[V \setminus (N_W \cup W)]) + 1$, whereas $\alpha (G) = \alpha (H[V \setminus (N_W \cup W)])$ in~\ref  {sub@fig:rank}, where $H = G \mid W$.}}{5}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {{$\alpha (G) = 3$}.}}}{5}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {{$W = \{ 0, 1, 2 \}$} and {$\alpha (G) = \alpha (H[V \setminus W]) = 3$}, where $H = G \mid W$.}}}{5}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {{$W = \{ 0, 1 \}$} and {$\alpha (H[V \setminus (N_W \cup W)]) = 2$}, where $H = G \mid W$.}}}{5}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {{$W = \{ 0, 2, 3 \}$} and {$\alpha (H[V \setminus W]) = 2$}, where $H = G \mid W$.}}}{5}}
\newlabel{newfig:alphaproj}{{2}{5}}
\newlabel{thm:liftfacet}{{1}{5}}
\newlabel{lem:cliqueproj}{{5}{5}}
\citation{Rossi.Smriglio.01}
\newlabel{newlem:cliqueproj}{{6}{6}}
\newlabel{eq:lemmalambda}{{5}{6}}
\newlabel{lem:aproxlambda}{{7}{6}}
\newlabel{eq:lambdabound}{{6}{6}}
\newlabel{coro:aproxlambda}{{2}{6}}
\newlabel{fig:sumrc1}{{3(a)}{7}}
\newlabel{sub@fig:sumrc1}{{(a)}{7}}
\newlabel{fig:sumrc2}{{3(b)}{7}}
\newlabel{sub@fig:sumrc2}{{(b)}{7}}
\newlabel{fig:sumrc3}{{3(c)}{7}}
\newlabel{sub@fig:sumrc3}{{(c)}{7}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Example of a sequence of edge projections such that the final lifted inequality is weaker than an intermediary one. Deleting false edges from $G^{(1)}$ does not increase the maximum size of a stable set.}}{7}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Graph $G = G^{(0)}$, $\alpha (G) = 3$. It generates the valid inequality $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 \leq 3$, which is the summation of the rank inequality $x_3 + x_4 + x_5 + x_6 + x_7 \leq 2$ with the clique one $x_1 + x_2 \leq 1$.}}}{7}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Graph $G^{(1)}$, $\alpha (G^{(1)}) = 2$, after projecting edge $(1,2)$ containing one false edge ($(3,5)$). It generates the inequality $x_3 + x_4 + x_5 + x_6 + x_7 \leq 2$, which is valid for $G$.}}}{7}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Graph $G^{(2)}$, $\alpha (G^{(2)}) = 1$, after projecting edge $(5,6)$ containing one false edge ($(4,7)$). It generates the inequality $x_3 + x_4 + x_7 \leq 1$, which is not valid for $G^{(1)}$.}}}{7}}
\newlabel{fig:sumrc}{{3}{7}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Strengthened Clique-Lifting}{7}}
\newlabel{newfig:sumrc1}{{4(a)}{8}}
\newlabel{sub@newfig:sumrc1}{{(a)}{8}}
\newlabel{newfig:sumrc2}{{4(b)}{8}}
\newlabel{sub@newfig:sumrc2}{{(b)}{8}}
\newlabel{newfig:sumrc3}{{4(c)}{8}}
\newlabel{sub@newfig:sumrc3}{{(c)}{8}}
\newlabel{newfig:sumrc3}{{4(d)}{8}}
\newlabel{sub@newfig:sumrc3}{{(d)}{8}}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Example of a sequence of clique projections. Deleting false edges from $G_1$ does not increase the maximum size of a stable set.}}{8}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Graph $G = G_0$, $\alpha (G) = 3$.}}}{8}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Graph $G_1$, $\alpha (G_1) = 3$, after projecting clique $\{0,1,2\}$ containing two false edges. It generates the inequality $x_1 + x_5 + x_6 + x_7 + x_4 + 2x_0 + 2x_2 + 2x_3 \leq 3$, which is valid for $G$ since to $\lambda _1 = 0$.}}}{8}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Graph $G_2$, $\alpha (G_2) = 2$, after projecting clique $\{ 0, 2, 3 \}$ containing several false edges. It generates the inequality $x_1 + x_5 + x_6 + x_7 + x_4 \leq 1$, which is not valid for $G_1$ due to $\lambda _2 = 2$.}}}{8}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {Graph $G_3$, $\alpha (G_3) = 2$, after projecting clique $\{ 0, 3, 4 \}$ containing one additional false edge. It generates the inequality $x_1 + x_5 + x_6 + x_7 + x_4 \leq 1$, which is valid for $G_2$ since $\lambda _3 = 0$.}}}{8}}
\newlabel{newfig:sumrc}{{4}{8}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Sufficient Conditions for Faceteness}{8}}
\citation{Rossi.Smriglio.01}
\citation{Rossi.Smriglio.01}
\citation{Campelo.Campos.Correa.08}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Example of a sequence of strengthened clique projections.}}{9}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Graph $G = G_0$, $\alpha (G) = 3$.}}}{9}}
\newlabel{lem:A}{{12}{9}}
\citation{Balas.Padberg.76,Campelo.Campos.Correa.08}
\citation{Rossi.Smriglio.01}
\@writefile{toc}{\contentsline {section}{\numberline {7}The cut-separating procedure}{10}}
\newlabel{fig:notrank}{{6(a)}{10}}
\newlabel{sub@fig:notrank}{{(a)}{10}}
\newlabel{fig:rank}{{6(b)}{10}}
\newlabel{sub@fig:rank}{{(b)}{10}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Structures leading to stronger inequalities than edge projection.}}{10}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Not rank inequality.}}}{10}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Rank inequality.}}}{10}}
\newlabel{fig:graph}{{6}{10}}
\newlabel{lem:W-proj}{{13}{10}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces Cut-generating procedure}}{11}}
\newlabel{alg:procedure}{{1}{11}}
\newlabel{eq:ineqexample}{{7}{11}}
\@writefile{toc}{\contentsline {section}{\numberline {8}Separation heuristic}{11}}
\newlabel{it:minweight}{{2}{11}}
\citation{Ostergard.01}
\citation{Pardalos}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces Maximal-clique based heuristic}}{12}}
\newlabel{alg:cliqueheu}{{2}{12}}
\@writefile{toc}{\contentsline {section}{\numberline {9}Preliminary computational experiments}{12}}
\citation{Rossi.Smriglio.01}
\citation{Rossi.Smriglio.01}
\citation{Pardalos}
\citation{Rossi.Smriglio.01}
\citation{Pardalos}
\citation{Pardalos}
\citation{Rossi.Smriglio.01}
\citation{Pardalos}
\citation{Pardalos}
\bibstyle{plain}
\bibdata{./stab}
\bibcite{Atamturk200040}{{1}{}{{}}{{}}}
\bibcite{Balas.Padberg.76}{{2}{}{{}}{{}}}
\bibcite{Bomze99themaximum}{{3}{}{{}}{{}}}
\bibcite{Campelo.Campos.Correa.08}{{4}{}{{}}{{}}}
\bibcite{LovaszPlummer86}{{5}{}{{}}{{}}}
\bibcite{ManninoSassano96}{{6}{}{{}}{{}}}
\bibcite{Ostergard.01}{{7}{}{{}}{{}}}
\@writefile{toc}{\contentsline {section}{\numberline {10}Conclusions}{13}}
\newlabel{tab:resultsDIMACS}{{9}{14}}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Version 1.0: Results with graphs selected from the DIMACS benchmark and with random graphs.}}{14}}
\newlabel{tab:resultsDIMACS}{{9}{15}}
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces Version 2.0: Results with graphs selected from the DIMACS benchmark and with random graphs.}}{15}}
\bibcite{Pardalos}{{8}{}{{}}{{}}}
\bibcite{Rossi.Smriglio.01}{{9}{}{{}}{{}}}
\bibcite{Segundo.Losada.Jimenez.11}{{10}{}{{}}{{}}}
\bibcite{Tomita.Kameda.07}{{11}{}{{}}{{}}}
\bibcite{XavierCampelo11}{{12}{}{{}}{{}}}
\providecommand\NAT@force@numbers{}\NAT@force@numbers
